//: [Previous](@previous)

/*:
 ### leetcode上第447号问题：Number of Boomerangs
 https://leetcode.com/problems/number-of-boomerangs/
 ```
 给定平面上 n 对不同的点，“回旋镖” 是由点表示的元组 (i, j, k) ，其中 i 和 j 之间的距离和 i 和 k 之间的距离相等（需要考虑元组的顺序）。
 找到所有回旋镖的数量。你可以假设 n 最大为 500，所有点的坐标在闭区间 [-10000, 10000] 中。
 示例:
 输入:
 [[0,0],[1,0],[2,0]]
 输出:
 2
 解释:
 两个回旋镖为 [[1,0],[0,0],[2,0]] 和 [[1,0],[2,0],[0,0]]
 ```
 */
import Foundation

// 先计算其他点到某个点的距离，统计相同的，可能会有n(n-1)种排序方法
// 时间复杂度 O(n^2)
// 空间复杂度 O(n)
func Solution(_ points: [[Int]]) -> Int {
    
    var num = 0
    var pointmap = [Int: Int]()
    for (i, pointi) in points.enumerated() {
        for (j, pointj) in points.enumerated() {
            if i == j {
                continue
            }
            let x = pointj[0]-pointi[0]
            let y = pointj[1]-pointi[1]
            let dis = x*x+y*y
            if let value = pointmap[dis] {
                 pointmap[dis] = value + 1
            } else {
                pointmap[dis] = 1
            }
        }
        for value in pointmap.values {
            num += value*(value-1)
        }
        pointmap.removeAll()
    }
    return num
}
Solution(
    [[0,0],[1,0],[-1,0],[0,1],[0,-1]])

//: [Next](@next)
